package site.wanjiahao;

public class CoinChange {

    static int[] coins = {25, 20, 5};

    // 递推实现
    // 既然41块钱是由前面确定其取值的，所以可以直接使用递推解决
    static int coinChange3(int n) {
        if (n <= 0) return 0;
        // 动态规划，存储数据的数值
        int[] dp = new int[n + 1];
        // 兑换n钱，最后需要的硬币面值为多少
//        int[] faces = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // 兑换i块钱需要的最少硬币
            // 对于它来说，也急速兑换i块钱，需要i - 1, i - 5, i - 10, i - 25，其中的最小值
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                // 确保数组不越界
                if (i >= coin && dp[i - coin] < min && dp[i - coin] != -1) {
                    min = Math.min(min, dp[i - coin]);
//                    faces[i] = coin;
                }
            }
            dp[i] = (min == Integer.MAX_VALUE)? -1: min + 1;
        }
//        print(faces, n);
        return dp[n];
    }

    private static void print(int[] faces, int n) {
        while (n > 0) {
            System.out.println(faces[n]);
            n = n - faces[n];
        }
    }

    // 找n分钱，最少需要多少硬币
    // 暴力递归，出现很多重复的计算
    static int coinChange1(int n) {
        // 越界
        if (n <= 0) return Integer.MAX_VALUE;
        // 确定边界条件
        if (contains(coins, n)) return 1;

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            min = Math.min(coinChange1(n - coin), min);
        }
        return min + 1;
    }

    // 记忆化搜索，存储计算过的值
    static int coinChange2(int n) {
        int[] rem = new int[n + 1];
        // 初始化记忆数组的初始条件
        for (int i : rem) {
            rem[i] = 1;
        }
        return coinChange2(n, rem);
    }

    static int coinChange2(int n, int[] rem) {
        // 越界
        if (n <= 0) return Integer.MAX_VALUE;
        if (rem[n] == 0) {
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                min = Math.min(coinChange1(n - coin), min);
            }
            rem[n] = min + 1;
        }
        return rem[n];
    }

    private static boolean contains(int[] coins, int i) {
        for (int coin : coins) {
            if (coin == i) {
                return true;
            }
        }
        return false;
    }

}
